// BinarySearch.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


/* Time Complexity: T(n) = T(n/2) + c 
   For every recursion, problem size reduce by half(b = 2) with only one problem of that size (a = 1)
                        and a constant amount of work 
*/

long BinarySearchRecur(long arr[], long x, long l, long r)
{    
    if(l <=  r)
    {
        long mid = (l + r) / 2;

        if(arr[mid] == x)
            return mid;
        else if(arr[mid] < x)
            return BinarySearchRecur(arr, x, mid+1, r);
        else
            return BinarySearchRecur(arr, x, l, mid-1);
    }
    return -1;
}

long BinarySearchIter(long arr[], long x, long l, long r)
{    
    int pos = -1;
    while(l <=  r)
    {
        long mid = (l + r) / 2;
        if(arr[mid] == x)
            return mid;
        else if(arr[mid] < x)        
            l = mid+1;       
        else
            r = mid-1;       
    }
    return -1;
}


int _tmain(int argc, _TCHAR* argv[])
{
    long arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr)/ sizeof(arr[0]);
    long x = 10;
    int result = BinarySearchRecur(arr, x, 0, n-1);
    (result == -1)? printf("Element is not present in array")
                 : printf("Element is present at index %d", result);
    getchar();
    return 0;	
}

